package com.linyaonan.leetcode.medium._1302;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * 给你一棵二叉树，请你返回层数最深的叶子节点的和。
 *输入：root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
 * 输出：15
 *  
 *
 * 提示：
 *
 * 树中节点数目在 1 到 10^4 之间。
 * 每个节点的值在 1 到 100 之间。
 *
 * @author: Lin
 * @date: 2020/1/14
 */
public class DeepestLeavesSum {
    List<Integer> ceng;
    List<Integer> value;
    public int deepestLeavesSum(TreeNode root) {
        ceng = new ArrayList<>();
        value = new ArrayList<>();
        dfs(root, 0);
        int maxCeng = ceng.get(0);
        int maxValue = value.get(0);
        for (int i = 1; i < ceng.size(); i++) {
            if (maxCeng < ceng.get(i)) {
                maxCeng = ceng.get(i);
                maxValue = value.get(i);
            } else if (maxCeng == ceng.get(i)) {
                maxValue += value.get(i);
            }
        }
        return maxValue;
    }

    private void dfs(TreeNode node, int count) {
        if (node != null) {
            if (node.left == null && node.right == null) {
                ceng.add(count);
                value.add(node.val);
            }
            ++count;
            dfs(node.left, count);
            dfs(node.right, count);
        }
    }
}
